# 给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。 
# 
#  回文字符串 是正着读和倒过来读一样的字符串。 
# 
#  子字符串 是字符串中的由连续字符组成的一个序列。 
# 
#  具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。 
# 
#  
# 
#  示例 1： 
# 
#  
# 输入：s = "abc"
# 输出：3
# 解释：三个回文子串: "a", "b", "c"
#  
# 
#  示例 2： 
# 
#  
# 输入：s = "aaa"
# 输出：6
# 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa" 
# 
#  
# 
#  提示： 
# 
#  
#  1 <= s.length <= 1000 
#  s 由小写英文字母组成 
#  
#  Related Topics 字符串 动态规划 
#  👍 688 👎 0


from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def countSubstrings(self, s: str) -> int:
        ans = 0

        def expand(string: str, left: int, right: int) -> None:
            while left >= 0 and right < len(string) and string[left] == string[right]:
                nonlocal ans
                ans += 1
                left -= 1
                right += 1

        for i in range(len(s)):
            expand(s, i, i)
            expand(s, i, i + 1)
        return ans


# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)


# 中心扩展
# 一个或两个为中心扩展, 是回文结果 + 1
#     def countSubstrings(self, s: str) -> int:
#         ans = 0
#
#         def expand(string: str, left: int, right: int) -> None:
#             while left >= 0 and right < len(string) and string[left] == string[right]:
#                 nonlocal ans
#                 ans += 1
#                 left -= 1
#                 right += 1
#
#         for i in range(len(s)):
#             expand(s, i, i)
#             expand(s, i, i + 1)
#         return ans

if __name__ == '__main__':
    s = Solution()
    str1 = 'abc'
    r1 = s.countSubstrings(str1)
    assert r1 == 3, r1

    str1 = 'aaa'
    r1 = s.countSubstrings(str1)
    assert r1 == 6, r1
